package leetcode.code1947;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int maxCompatibilitySum(int[][] students, int[][] mentors) {
		int m = mentors.length, n = mentors[0].length;
		// 压缩学生答案
		int[] sa = this.answer(m, n, students);
		// 压缩导师答案
		int[] ma = this.answer(m, n, mentors);
		// 最大状态数量，可用状态数量
		int limit = 1 << m;
		Integer[] dp = new Integer[limit];
		// n道题，学生答案sa，导师答案ma，匹配完状态limit -1，当前已经匹配的导师状态0，当前匹配学生索引0，缓存。
		return this.maxCompatibilitySum(n, sa, ma, limit - 1, 0, 0, dp);
	}

	private int maxCompatibilitySum(int n, int[] sa, int[] ma, int limit, int used, int index, Integer[] dp) {
		if (limit == used) {
			return 0;
		}
		if (dp[used] != null) {
			return dp[used];
		}
		int comp = 0;
		int stu = sa[index];
		for (int i = 0; i < ma.length; i++) {
			int pos = 1 << i;
			// i导师可以参与当前匹配
			if ((used & pos) == 0) {
				// 匹配得分
				int score = this.score(stu, ma[i], n);
				// i导师匹配index学生的最大得分 == 后续最大得分 + 当前得分。
				comp = Math.max(comp, this.maxCompatibilitySum(n, sa, ma, limit, used | pos, index + 1, dp) + score);
			}
		}
		dp[used] = comp;
		return comp;
	}

	// n题情况下， 学生和导师得分情况
	private int score(int student, int mentor, int n) {
		int compare = student ^ mentor;
		int ans = 0;
		for (int i = 0; i < n; i++) {
			if ((compare & (1 << i)) == 0) {
				ans++;
			}
		}
		return ans;
	}

	// 压缩答案
	private int[] answer(int m, int n, int[][] arr) {
		int[] ans = new int[m];
		for (int i = 0; i < m; i++) {
			int answer = 0;
			for (int j = 0; j < n; j++) {
				answer |= arr[i][j] << j;
			}
			ans[i] = answer;
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(8, this.maxCompatibilitySum(H.str2array1("[[1,1,0],[1,0,1],[0,0,1]]"),
				H.str2array1("[[1,0,0],[0,0,1],[1,1,0]]")));
		H.compare(0,
				this.maxCompatibilitySum(H.str2array1("[[0,0],[0,0],[0,0]]"), H.str2array1("[[1,1],[1,1],[1,1]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
